package com.lm.leetcode.theDifficultyOfQuestionBank;

/**
 * @Auther: Min.Liu
 * @Date: Created in 9:00 2025/5/21
 * @Description:
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 *
 * 示例 1：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */
public class findMedianSortedArraysDemo {
    public static void main(String[] args) {
        findMedianSortedArraysDemo demo = new findMedianSortedArraysDemo();
        int[] arr1 = {1,3,5};
        int[] arr2 = {2,4,4};
        System.out.println(demo.findMedianSortedArrays(arr1, arr2));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        //假如总长为奇数 【0，1，2】，找第2小 ，找两次除2仍是中位数
        //为偶数，【0，1，2，3】，找第2小和第3小，算中位数
        int kLeft = (n + m + 1) / 2; //3得2  4得2
        int kRight = (n + m + 2) / 2; //3得2  4得3
        return ((getKth(nums1, 0, n - 1, nums2, 0, m - 1, kLeft) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, kRight)) / 2.0);
    }

    //第K小对应数组下标+1 比如说第2小就是下标为1再加1
    //二分去除部分元素，注意二分时保持数组都是左闭右闭区间
    //k是第几小，是从1开始计数的，注意与索引从0开始区分概念！
    public int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        //两个数组剩余长度
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if (len1 > len2) { //保证第2个数组长,如果有空一定是数组1
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        }
        if (len1 == 0) { //数组1空了，直接在数组2返回目前的第k小
            return nums2[start2 + k - 1];
        }
        if (k == 1) { //当前要找第1小 返回两数组剩下部分头部较小的那个
            return Math.min(nums1[start1], nums2[start2]);
        }
        //注意这里的i，j是第几小对应的数组索引，所以要-1
        int i = start1 + Math.min(len1, k / 2) - 1; //如果当前的k划分一半 大于数组长，那直接指向数组末端
        int j = start2 + Math.min(len2, k / 2) - 1;
        if (nums1[i] > nums2[j]) { //nums2从j开始 往前的所有元素都去除
            k = k - (j - start2 + 1); //括号内表示去除的元素数量，更新k，继续找剩下第k小
            j = j + 1; //左闭
            return (getKth(nums1, start1, end1, nums2, j, end2, k));
        } else {
            k = k - (i - start1 + 1);
            i = i + 1;
            return (getKth(nums1, i , end1, nums2, start2, end2, k));
        }
    }
}
